from typing import List

# 139. 单词拆分
# 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
# 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
def wordBreak(s: str, wordDict: List[str]) -> bool:
    # dp 数组，存放任意位置的字符串，是否可以由列表拼接
    dp = [False] * (len(s) + 1)
    dp[0] = True
    # 从第一个字符串开始遍历
    for s_index in range(1, len(s) + 1):
        # 遍历列表
        for word in wordDict:
            word_len = len(word)
            # 如果发现已经可以由字符串拼接，跳出当前循环
            if dp[s_index]:
                continue
            # 保证字符串切片的时候，不会出现数组越界
            if word_len <= s_index:
                match_s = s[s_index - word_len:s_index]
                if word == match_s:
                    dp[s_index] = True and dp[s_index - word_len]
    return dp[len(s)]


s_1 = "leetcode"
wordDict_1 = ["leet", "code"]
result = wordBreak(s_1, wordDict_1)
print(f"result:{result}")

s_1 = "applepenapple"
wordDict_1 = ["apple", "pen"]
result = wordBreak(s_1, wordDict_1)
print(f"result:{result}")

s_1 = "catsandog"
wordDict_1 = ["cats", "dog", "sand", "and", "cat"]
result = wordBreak(s_1, wordDict_1)
print(f"result:{result}")
